#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (auto num : nums)
            sum += num;
        if (S > 1000 || (S + sum) % 2 != 0)
            return 0;
        vector<int>dp0(2001);
        vector<int>dp1(2001);
        dp0[1000 + nums[0]] += 1;
        dp0[1000 - nums[0]] += 1;
        for (int i = 1; i < nums.size(); ++i) {
            for (int j = 0; j < 2001; ++j) {
                dp1[j] = 0;
                if (j - nums[i] >= 0)
                    dp1[j] += dp0[j - nums[i]];
                if (j + nums[i] <= 2000)
                    dp1[j] += dp0[j + nums[i]];
            }
            swap(dp0, dp1);
        }
        return dp0[S + 1000];
    }
};